package data_structures_and_algorithms.recursion_traceback.learn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @ClassName Code_note_01_printAll_sub_sequence
 * @Description: TODO
 * @Author: myl
 * @create_time: 2022/10/31 00:33
 */
public class Code_note_01_printAll_sub_sequence {

    // 打印字符串的所有子序列
    public static class PrintAllSubSequence{
        public static void main(String[] args) {
            String str = "abcd";
            System.out.println(Arrays.toString(printAllSubSeq(str).toArray()));
        }

        public static List<String> printAllSubSeq(String string){
            if (string == null || string.length() == 0)
                return new ArrayList<>();
            List<String> list = new ArrayList<>((int)Math.pow(2, string.length()));
            char[] chars = string.toCharArray();
            process(chars, 0, list, new StringBuilder());
            return list;
        }

        private static void process(char[] chars, int index, List<String> list, StringBuilder stringBuilder) {
            // 判断是否满足打印条件，满足即打印 结束方法
            if (index == chars.length){
                list.add(stringBuilder.toString());
                return;
            }

            // 改变状态向下继续递归

            // 使用当前字符
            stringBuilder.append(chars[index]);
            process(chars, index + 1, list, stringBuilder);
            stringBuilder.deleteCharAt(stringBuilder.length() - 1);

            // 不使用当前字符
            process(chars, index + 1, list, stringBuilder);
        }
    }

    // 打印字符串的所有子序列(不可以带有重复字符)   ----搞一个Set集合去存储，天然去重
    public static class PrintAllSubSequenceWithNoRepeat {


    }

}
